package jianzhioffer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/24 10:28
 * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
 */
public class offer_57_和为s的两个数字 {

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(twoSum1(nums, target)));
    }

//    暴力双重遍历，不推荐,超出时间限制
    public static int[] twoSum1(int[] nums, int target) {
        int[] res = new int[2];
        for (int i=0; i<nums.length; i++){
            for (int j=i; j<nums.length; j++){
                if (nums[i]+nums[j]==target){
                    res[0] = nums[i];
                    res[1] = nums[j];
                    return res;
                }
            }
        }
        return res;
    }

//哈希表，好像也超时了
    public static int[] twoSum2(int[] nums, int target) {
        int[] res = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++){
            if (map.containsValue(target-nums[i])){
                res[0] = nums[i];
                res[1] = target-nums[i];
                return res;
            }else map.put(i, nums[i]);
        }
        return res;
    }

    // 集合，符合，但效率不高
    public static int[] twoSum3(int[] nums, int target) {
        int[] res = new int[2];
        HashSet<Integer> set = new HashSet<>();
        for (int i=0; i<nums.length; i++){
            if (set.contains(target-nums[i])){
                res[0] = nums[i];
                res[1] = target - nums[i];
                return res;
            }else set.add(nums[i]);
        }
        return res;
    }

//    双指针
    public static int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        int i = 0, j = nums.length - 1;
        while (i<j){
            if (nums[i]+nums[j]==target){
                res[0]=nums[i];
                res[1]=nums[j];
                return res;
            }else if (nums[i]+nums[j]>target) j--;
            else i++;
        }
        return res;
    }
}
